home *** CD-ROM | disk | FTP | other *** search
/ Over 1,000 Windows 95 Programs / Over 1000 Windows 95 Programs (Microforum) (Disc 1).iso / 1249 / binary.t < prev    next >
Text File  |  1997-04-18  |  3KB  |  189 lines
  1. %
  2. % "binary.t" sorts words using a binary tree
  3. %
  4. %   Sample program for the T Interpreter by:
  5. %
  6. %   Stephen R. Schmitt
  7. %   962 Depot Road
  8. %   Boxborough, MA 01719
  9. %
  10.  
  11. type word : record
  12.                 left  : int
  13.                 right : int
  14.                 item  : string
  15.             end record
  16.  
  17. var next_word : string
  18.  
  19. const root : int := 0
  20. var next   : int := root
  21. const size : int := 10
  22.  
  23. var list : array[size] of word
  24.  
  25.  
  26. program
  27.  
  28.     var i : int
  29.  
  30.     % initialize the list
  31.     for i := root...size-1 do
  32.  
  33.         list[i].right := 0
  34.         list[i].left := 0
  35.         list[i].item := ""
  36.  
  37.     end for
  38.  
  39.     % get words
  40.     for i := root...size-2 do
  41.  
  42.         prompt "word " & intstr( i + 1, 2 ) & " : "
  43.         get next_word
  44.         
  45.         exit when next_word = ""
  46.  
  47.         if lookup( next_word ) then
  48.  
  49.             put "duplicate"
  50.  
  51.         else
  52.  
  53.             insert( next_word )
  54.  
  55.         end if
  56.  
  57.     end for
  58.  
  59.     put ""
  60.  
  61.     traverse( 1 )
  62.  
  63. end program
  64.  
  65.  
  66. function new_item : int
  67.  
  68.     next := next + 1
  69.     assert next < size
  70.     return next
  71.  
  72. end function
  73.  
  74.  
  75. function lookup( word : string ) : boolean
  76.  
  77.     var i : int := root
  78.     var found, done : boolean
  79.  
  80.     done := false
  81.  
  82.     loop
  83.  
  84.         if word = list[i].item then
  85.  
  86.             found := true
  87.             done := true
  88.  
  89.         end if
  90.  
  91.         exit when done
  92.  
  93.         if word > list[i].item then
  94.  
  95.             if list[i].right = 0 then
  96.  
  97.                 found := false
  98.                 done := true
  99.  
  100.             else
  101.  
  102.                 i := list[i].right
  103.  
  104.             end if
  105.  
  106.         else
  107.  
  108.             if list[i].left = 0 then
  109.  
  110.                 found := false
  111.                 done := true
  112.  
  113.             else
  114.  
  115.                 i := list[i].left
  116.  
  117.             end if
  118.  
  119.         end if
  120.  
  121.         exit when done
  122.  
  123.     end loop
  124.  
  125.     return found
  126.  
  127. end function
  128.  
  129.  
  130. procedure insert( word : string )
  131.  
  132.     var i, j : int
  133.     var done : boolean
  134.  
  135.     i := root
  136.     done := false
  137.  
  138.     loop
  139.  
  140.         if word > list[i].item then
  141.  
  142.             if list[i].right = 0 then
  143.  
  144.                 j := new_item
  145.                 list[i].right := j
  146.                 list[j].item := word
  147.                 done := true
  148.  
  149.             else
  150.  
  151.                 i := list[i].right
  152.  
  153.             end if
  154.  
  155.         else
  156.  
  157.             if list[i].left = 0 then
  158.  
  159.                 j := new_item
  160.                 list[i].left := j
  161.                 list[j].item := word
  162.                 done := true
  163.  
  164.             else
  165.  
  166.                 i := list[i].left
  167.  
  168.             end if
  169.  
  170.         end if
  171.  
  172.         exit when done
  173.  
  174.     end loop
  175.  
  176. end procedure
  177.  
  178.  
  179. procedure traverse( node : int )
  180.  
  181.     if node ~= 0 then
  182.  
  183.         traverse( list[node].left )
  184.         put list[node].item
  185.         traverse( list[node].right )
  186.  
  187.     end if
  188.  
  189. end procedure